home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / grabst / proper.c < prev    next >
C/C++ Source or Header  |  1990-03-06  |  9KB  |  345 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /* proper.c contains procedures to make a proper matrix for a digraph. */
  9.  
  10. #include "malloc.h"
  11. #include "digraph.h"
  12. #include "debug.h"
  13. #include "list.h"
  14.  
  15. OUTEDGE *get_edge();
  16.  
  17. make_proper(digraph)
  18. DIGRAPH *digraph;
  19.   /**
  20.      make_proper makes a proper reachability matrix for digraph.
  21.    **/
  22. {
  23.     if (debug1)
  24.     {
  25.         print_size(digraph, "Size before making proper: \n\t");
  26.     }
  27.  
  28.     make_closure(digraph);  /* compute trasitive closure of succedents */
  29.     find_levels(digraph);   /* partition into levels */
  30.     undo_closure(digraph);  /* restore original edges */
  31.     shorten_spans(digraph); /* add dummies to shorten spans over one level */
  32.  
  33.     if (debug1)
  34.     {
  35.         print_size(digraph, "Size after making proper: \n\t");
  36.     }
  37. } /* make_proper */
  38.  
  39. make_closure(digraph)
  40. DIGRAPH *digraph;
  41.   /** 
  42.      make_closure computes the transitive closure of the succeedent set
  43.      of each node in digraph.
  44.    **/
  45. {
  46.     SET *closed_set;   /* closed version of the set */
  47.     NODE *node;        /* the current node */
  48.     VNO root_vno;      /* vno of current node */
  49.     VNO to_vno;        /* each to vertex # */
  50.  
  51.     init_set(closed_set);
  52.  
  53.     each_node(digraph, node)
  54.     loop
  55.         root_vno = Vno(node);
  56.         add_element(closed_set, root_vno);    /* node is in its closure */
  57.     
  58.         each_element(Succ_set(node), to_vno)
  59.         loop
  60.         close_set(digraph, closed_set, to_vno, root_vno);
  61.         endloop
  62.     
  63.         copy_set(Succ_set(node), closed_set);
  64.         clear_set(closed_set);
  65.    
  66.         each_element(Succ_set(node), to_vno)   /* fix up antecedents */
  67.         loop
  68.         add_element(Ante_set(Node(digraph, to_vno)), root_vno);
  69.         endloop
  70.     endloop
  71. } /* make_closure */
  72.  
  73. close_set(digraph, closed_set, vno, root_vno)
  74. DIGRAPH *digraph;
  75. SET *closed_set;     /* set to add to */
  76. VNO vno;             /* next succedent node */
  77. VNO root_vno;         /* vno of root node */
  78.   /**
  79.      close_set adds the closure of vno's succedents to closed_set.  If a 
  80.      cycle is detected, the last edge in the cycle is reversed, to
  81.      break the cycle.
  82.    **/
  83. {
  84.     VNO to_vno;    /* each succedent of vno */
  85.  
  86.     if (!in(closed_set, vno))
  87.     {
  88.         add_element(closed_set, vno);
  89.  
  90.         each_element(Succ_set(Node(digraph, vno)), to_vno)
  91.         loop
  92.         if (to_vno == root_vno)    /* found cycle */
  93.         {
  94.         int i;
  95.  
  96.             if (debug1)
  97.         {
  98.                 printf("close_set: edge %s to %s completes cycle\n",
  99.                    Name(Node(digraph, vno)), 
  100.                Name(Node(digraph, root_vno)));
  101.         }
  102.  
  103.         for (i = max_edges(Node(digraph, vno), Node(digraph, root_vno));
  104.              i > 0;
  105.              i--)
  106.         {
  107.             if (get_edge(digraph, Node(digraph, vno), 
  108.                  Node(digraph, root_vno), i) != NULL)
  109.             {
  110.                     reverse_edge(digraph, vno, root_vno, i);
  111.             }
  112.         }
  113.         }
  114.         else            /* no cycle yet */
  115.         {
  116.             close_set(digraph, closed_set, to_vno, root_vno);
  117.         }
  118.         endloop
  119.     }
  120. } /* close_set */
  121.  
  122. find_levels(digraph)
  123. DIGRAPH *digraph;
  124.   /**
  125.      find_levels partitions the nodes of digraph into levels.
  126.    **/
  127. {
  128.     LIST *difflist;  /* list of set differences */
  129.     ITEM *diff;      /* each diff item */
  130.     SET *diff_set;   /* each difference */
  131.     SET *level_set;  /* each level_set */
  132.     int levno = 0;   /* level_set number for debugging */
  133.     NODE *node;      /* each node */
  134.  
  135.     init_list(difflist);
  136.     init_set(diff_set);           /* initialize the set */
  137.  
  138.     each_node(digraph, node)
  139.     loop
  140.         copy_set(diff_set, Succ_set(node));
  141.         intersect(diff_set, Ante_set(node));   /* compute the intersection */
  142.         xor(diff_set, Succ_set(node));         /* compute the difference */
  143.         add_item(difflist, Vno(node), diff_set);
  144.     
  145.         if (debug)
  146.         {
  147.         printf("\n\nNode = %s:  Succedents: ", Name(node));
  148.         print_set(digraph,  Succ_set(node));
  149.         printf("\nAntecedents: ");
  150.         print_set(digraph, Ante_set(node));
  151.         printf("\nDifference: ");
  152.         print_set(digraph, diff_set);
  153.         printf("\n");
  154.         }
  155.     endloop
  156.  
  157.     init_set(level_set);
  158.  
  159.     do
  160.     {
  161.         if (debug)
  162.         {
  163.         printf("\n\nDiff list is:  ");
  164.  
  165.         each_item(difflist, diff)
  166.         loop
  167.             printf(" %s ", Name(Node(digraph, Key(diff))));
  168.         endloop
  169.  
  170.         printf("\n\n\nLevel %d:  ", levno++);
  171.         }
  172.  
  173.         each_item(difflist, diff)
  174.         loop
  175.         if (empty(Set(diff)))   /* no differences */
  176.         {
  177.             if (debug)
  178.             {
  179.                 printf(" %s ", Name(Node(digraph, Key(diff))));
  180.         }
  181.  
  182.             fflush(stdout);
  183.  
  184.             add_element(level_set, Key(diff));
  185.             remove_item(difflist, diff);
  186.         }
  187.         endloop
  188.  
  189.         each_item(difflist, diff)
  190.         loop
  191.         difference(Set(diff), level_set);
  192.         endloop
  193.  
  194.         add_level(digraph, level_set);
  195.         clear_set(level_set);    /* clear the level_set */
  196.     } while (!empty_list(difflist));
  197.  
  198.     {
  199.         LEVEL *level;   /* each level */
  200.  
  201.         levno = 0;
  202.  
  203.         each_level(digraph, level)   /* assign level numbers */
  204.         loop
  205.         Lno(level) = levno++;
  206.         endloop
  207.     }
  208.  
  209.     if (debug)
  210.     {
  211.         print_levels(digraph);
  212.     }
  213. } /* find_levels */
  214.  
  215. undo_closure(digraph)
  216. DIGRAPH *digraph;
  217.   /**
  218.      undo_closure restores the antecedent and succedent sets of each node in
  219.      digraph to their value before make_closure() was invoked.  This is done
  220.      by traversing the edge list of each node.
  221.    **/
  222. {
  223.     NODE *node;         /* each node */
  224.  
  225.     each_node(digraph, node)
  226.     loop
  227.         clear_set(Succ_set(node));  /* clear the succedents */
  228.         clear_set(Ante_set(node));  /* clear the antecedents */
  229.     endloop
  230.  
  231.     fix_ante_succ_sets(digraph);
  232. } /* undo_closure */
  233.  
  234. shorten_spans(digraph)
  235. DIGRAPH *digraph;
  236.   /**
  237.      shorten_spans shortens spans with length greater than one by adding dummy
  238.      nodes to succeeding levels of digraph.
  239.    **/
  240. {
  241.     LEVEL *level;       /* each level */
  242.     MEMBER *member;     /* each member */
  243.     SET *long_spans;    /* set of nodes to have dummies */
  244.     SET *ante_set;      /* antecedents of dummies */
  245.     VNO vno;            /* vno of each long span */
  246.  
  247.     init_set(long_spans);    /* initialize */
  248.     init_set(ante_set); 
  249.  
  250.     each_level(digraph, level)
  251.     loop
  252.         if (Next_level(level) != NULL)
  253.     {
  254.             each_member(level, member)
  255.             loop
  256.               /* compute succedents not in the next level */
  257.             copy_set(long_spans, Succ_set(Member_node(member)));
  258.             difference(long_spans, Members(Next_level(level)));
  259.  
  260.             if (debug)
  261.             {
  262.                 printf("shorten_spans:  long spans for '%s': ", 
  263.                    Name(Member_node(member)));
  264.  
  265.                 each_element(long_spans, vno)
  266.                  loop
  267.                     printf(" %s", Name(Node(digraph, vno)));
  268.                 endloop
  269.  
  270.                 printf("\n");
  271.             }
  272.  
  273.             each_element(long_spans, vno)
  274.          loop
  275.                   /* compute antecedents on the current level */
  276.                 copy_set(ante_set, Ante_set(Node(digraph, vno)));
  277.                 intersect(ante_set, Members(level));
  278.  
  279.                   /** 
  280.              add a dummy node to the next level -- 
  281.                  fix up antecedents 
  282.                **/
  283.                 add_dummy(digraph, Next_level(level), vno, ante_set); 
  284.  
  285.                 if (debug)
  286.                 {
  287.                     printf("\n\nshorten_spans: shortened %s -> %s span:\n",
  288.                        Name(Member_node(member)),
  289.                        Name(Node(digraph, vno)));
  290.                     print_levels(digraph);
  291.                 }
  292.             endloop
  293.             endloop
  294.     }
  295.     endloop
  296.  
  297.     if (debug)
  298.     {
  299.         printf("\nshorten_spans:\n");
  300.         print_levels(digraph);
  301.     }
  302. } /* shorten_spans */
  303.  
  304. print_size(digraph, message)
  305. DIGRAPH *digraph;
  306. char *message;
  307.   /**
  308.      print_size goes through the digraph and counts the number of nodes and
  309.      edges, and prints out that information along with the message text.
  310.    **/
  311. {
  312.     NODE *node;
  313.     int n_nodes, n_real, n_dummy, n_coalesced, n_coalescer;
  314.     int n_arc;
  315.  
  316.     n_nodes = n_real = n_dummy = n_coalesced = n_coalescer = 0;
  317.     n_arc = 0;
  318.  
  319.     all_nodes(digraph, node)
  320.     loop
  321.         if (Is_dummy(node))
  322.         {
  323.         n_dummy++;
  324.         n_arc++;
  325.         }
  326.     else if (Coalescer(node))
  327.     {
  328.         n_coalescer++;
  329.         n_arc += card(Succ_set(node));
  330.     }
  331.         else if (Coalesced(node))
  332.         {
  333.         n_coalesced++;
  334.         }
  335.         else
  336.         {
  337.         n_real++;
  338.            n_arc += card(Succ_set(node));
  339.         }
  340.     endloop
  341.  
  342.     n_nodes = n_real + n_dummy;
  343.     printf("%s %d nodes (%d real, %d dummy %d coalescer %d coalesced), %d arcs.\n", message, n_nodes, n_real, n_dummy, n_coalescer, n_coalesced, n_arc);
  344. } /* print_size */
  345.